package tree.leetcode_538_medium;

public class ConvertBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(1);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(5);
        new ConvertBST().convertBST2(root);
    }
    static int sum = 0;
    public static TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        //反向中序遍历，先右后左
        convertBST(root.right);
        //在中间 " 做事 "
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }

    //不是用全局变量的操作
    public TreeNode convertBST2(TreeNode root){
        dfs(root,0);
        return root;
    }
    public int dfs(TreeNode root, int sum){
        //需要设计一个变量来记录累加的结果。
        if(root == null){
            return sum;
        }
        //反向中序遍历
        sum = dfs(root.right, sum);
        root.val += sum;
        sum = root.val;
        sum = dfs(root.left, sum);

        return sum;
    }

}
